Problem :

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1 :

**Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4**

Example 2 :

**Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1**

Example 3 :

**Input: nums = [1], target = 0
Output: -1**

核心思維 :

1. 利用 (right + left) / 2 搜尋陣列的中間值 nums[mid]
2. 進行二分搜尋法持續至找出並回傳目標值 target

• 若中間值 nums[mid] 與 目標值 target 相等，則回傳中間值 nums[mid]

• 若中間值 nums[mid] 小於等於 目標值 target ，將左指標設定為中間值 nums[mid] + 1

• 若中間值 nums[mid] 大於等於 目標值 target ，將右指標設定為中間值 nums[mid] - 1

  3. 當二分搜尋法的搜尋結束後仍未找到目標值 target ， 則回傳-1

程式碼 :

class Solution {
public:
    int search(vector<int>& nums, int target) {
        //設定左指標索引值為0，右指標索引值為陣列長-1
        int left = 0, right = nums.size() - 1;  
        while ( left <= right) {
            //設定中間值
            int mid = (right + left) / 2;       
            //當中間值與目標值相同，回傳目標值
            if (nums[mid] == target) {          
                return mid;
            }
            //檢查左半邊是否排序
            if (nums[left] <= nums[mid]) {
                //確認目標值介於左指標與中間值之間
                if (nums[left] <= target && target < nums[mid]) {
                    //目標在左半邊，調整右指標
                    right = mid - 1;
                }
                else {
                    //目標在右半邊，調整左指標
                    left = mid + 1;
                }
            }
            else {
                //檢查右半邊是否排序
                if (nums[right] >= target && target > nums[mid]) {
                    //目標在右半邊，調整左指標
                    left = mid + 1;
                }
                else {
                    //目標在左半邊，調整右指標
                    right = mid - 1;
                }
            }
        }
        //若未找到目標值，回傳-1
        return -1;
    }
};

結論 :

這裡利用二分搜尋法來處理排序陣列的問題，首先找出中間值並利用目標值的大小來決定接下來尋找目標值得方向，重複利用相同的步驟縮小搜尋範圍，持續至找到且回傳目標值或是發現目標值不在範圍內並回傳-1，二元搜尋法在處理搜尋有序陣列的問題中是相當實用的演算法。